package mc0447;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
	// 数据长度
	public static int N;
	// 线段树原数组，下标从1开始计算
	public static long[] a;

	// 输入优化模板开始
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StreamTokenizer st = new StreamTokenizer(br);

	static long rd() throws IOException {
		st.nextToken();
		return (long) st.nval;
	}

	// 输入优化模板结束
	static int n, q;
	// static long[] a;
	static long[] pa; // a的前缀和
	static int l, r;

	// 长度1000000的st表数组的k值最大不会超过20
	static int[][] dp;

	// 建立ST表
	// ST保存的是最大值的在数组中的位置
	static void stInit() {
		// 区间长度为1，直接赋值
		// 数据长度为n
		for (int i = 1; i <= n; i++) {
			dp[i][0] = i;
		}

		// 计算k的最大值p，p=log2(数据总长度)
		// 2的p次方小于等于数据长度，2的p+1次方大于数据总长度
		// Math.log()计算e为底的对数，这里用了数学中的换底公式
		// 数据长度为n
		int p = (int) (Math.log(n) / Math.log(2.0));

		// 递推计算st表
		// 位运算1<<k表示2的k次方
		// 位运算1<<(k-1)表示2的k-1次方
		// n表示数据长度
		// s、k参见资料文档
		for (int k = 1; k <= p; k++) {
			for (int s = 1; s + (1 << k) <= n + 1; s++) {
				// dp[s][k]区间由组成他的两个小区间构成
				//dp[s][k] = Math.max(dp[s][k - 1], dp[s + (1 << (k - 1))][k - 1]);
				int left = dp[s][k-1];
				int right = dp[s + (1 << (k - 1))][k - 1];
				dp[s][k] = (a[left]>a[right])?left:right;
			}
		}
	}

	// L、R表示左右端点
	// 返回区间最大值
	static int stQuery(int L, int R) {
		// 计算k的值
		// 2的k次方小于查询区间长度，2的k+1次方大于查询区间长度
		// Math.log()计算e为底的对数，这里用了数学中的换底公式
		int k = (int) (Math.log(R - L + 1) / Math.log(2.0));
		int pos1 = dp[L][k];
		int pos2 = dp[R - (1 << k) + 1][k];
		
		// 两个小区间拼出被查询区间
		//return Math.max(dp[L][k], dp[R - (1 << k) + 1][k]);
		return (a[pos1]>a[pos2])?pos1:pos2;
	}

	public static void main(String[] args) throws IOException {
		n = (int) rd();
		q = (int) rd();

		a = new long[n + 1];
		pa = new long[n + 1];
		N = n+5;
		// 长度1000000的st表数组的k值最大不会超过20
		dp = new int[N][25];

		// 下标1开始
		for (int i = 1; i <= n; i++) {
			long temp = rd();
			a[i] = temp;
			pa[i] = pa[i - 1] + temp;
		}

		//建立ST表
		stInit();
		
		
		StringBuilder sb = new StringBuilder();
		while (q > 0) {
			q--;
			l = (int) rd();
			r = (int) rd();
			long ans = 0;
			// 找[l,r]最大值
			int pos = stQuery(l, r);
			long d = a[pos];
			// 计算公式：d*(r-pos)减去[pos+1,r]区间的和
			ans += d * (r - pos) - (pa[r] - pa[pos]);
			//System.out.printf("%d,%d,%d,%d,%d\n",d,pos,ans,l,r);
			r = pos - 1;
			while (r - l > 0) {
				pos = stQuery(l, r);
				d = a[pos];
				// 计算公式：d*(r-pos)减去[pos+1,r]区间的和
				ans += d * (r - pos) - (pa[r] - pa[pos]);
				//System.out.printf("%d,%d,%d,%d,%d\n",d,pos,ans,l,r);
				r = pos - 1;
			}
			sb.append(ans);
			sb.append("\n");
		}
		System.out.print(sb.toString());
	}

}
